import java.util.*;

/**
 * @Author 12629
 * @Description：
 */
public class Test {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0; i< nums.length;i++) {
            ret ^= nums[i];
        }
        return ret;
    }

    public int singleNumber2(int[] nums) {

        Set<Integer> set = new HashSet<>();
        for(int i = 0;i < nums.length;i++) {
            int key = nums[i];
            if(!set.contains(key)) {
                set.add(nums[i]);
            }else {
                set.remove(key);
            }
        }
        //走到这里  集合当中  只剩下一个元素了  问题：如何找到这个元素
        for(int i = 0;i < nums.length;i++) {
            int key = nums[i];
            if(set.contains(key)) {
                return nums[i];
            }
        }
        return -1;
    }

    /*public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        //1、第一次遍历链表
        Node cur = head;
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        //2、第二次遍历链表
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }*/

    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        //把宝石存储在集合当中
        for(char ch : jewels.toCharArray()) {
            set.add(ch);
        }

        int count = 0;
        //遍历石头 查看石头当中 有多少个宝石
        for(char ch : stones.toCharArray()) {
            if(set.contains(ch)) {
                count++;
            }
        }
        return count;
    }



    public static List<String> topKFrequent(String[] words, int k) {
        //1. 统计单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for(String key : words) {
            if(map.get(key) == null) {
                map.put(key,1);
            }else {
                int val = map.get(key);
                map.put(key,val+1);
            }
        }

        //2.建立大小为k的    小根堆
        PriorityQueue<Map.Entry<String,Integer> > minQ =
                new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //频率相同的时候  把这个变成以key 为准的大根堆
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());//根据频率
            }
        });

        //3. 遍历map，先放满K个，然后从第K+1个开始 和堆顶元素比较
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            //3.1 如果小根堆没有放满k个 那么直接放进去
            if(minQ.size() < k) {
                minQ.offer(entry);
            }else {
                //3.2 如果已经方面了小根堆，那么 我们需要让当前元素 和堆顶元素比较
                Map.Entry<String,Integer> top = minQ.peek();
                if(top != null) {
                    if (entry.getValue() > top.getValue()) {
                        minQ.poll();
                        minQ.offer(entry);
                    } else {
                        //<  ||  ==  3.3 此时考虑频率相同，key小的入队
                        if (top.getValue().compareTo(entry.getValue()) == 0) {
                            if (top.getKey().compareTo(entry.getKey()) > 0) {
                                minQ.poll();
                                minQ.offer(entry);
                            }
                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minQ.poll();
            if(top != null) {
                ret.add(top.getKey());
            }
        }
        Collections.reverse(ret);
        return ret;
    }

    public int firstUniqChar(String s) {
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            count[ch-97]++;
        }

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(count[ch-97] == 1) {
                return i;
            }
        }
        return -1;
   }

    public static void main(String[] args) {
       // String[] strings = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        String[] strings = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> ret = topKFrequent(strings,3);
        System.out.println(ret);
    }
}
